package com.example.lib5.sort;

import com.example.lib5.sort.array.MyArray;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
        //数组
        int[] arr={53,3,542,748,14,214};
        System.out.println(Arrays.toString(arr));
        radixSortTestB(arr);
        System.out.println(Arrays.toString(arr));

//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        Date date1 = new Date();
//        String date1Str = simpleDateFormat.format(date1);
//        System.out.println("排序前的时间：" + date1Str);
//        radixSort(MyArray.getBigArr(80000000));
//        Date date2 = new Date();
//        String date2Str = simpleDateFormat.format(date2);
//        System.out.println("排序前的时间：" + date2Str);

    }

    private static void radixSort(int[] arr) {
        //arr里面最大的那个值是多少，然后获取那个值的位数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int size = String.valueOf(max).length();
        System.out.println(size);
        //中转的二维数组
        int[][] bucket = new int[10][arr.length];
        //每一个数组的个数
        int[] bucketElementCount = new int[10];
        for (int i = 0, n = 1; i < size; i++, n *= 10) {
            /**
             * 第i轮
             * 1.将arr的数据根据个位数从小到大依次添加到二维数组
             * 2.将中转数组从小到大遍历取值，添加到arr
             */
            for (int j = 0; j < arr.length; j++) {
                //获取i数组值得个位数，然后根据个位数的值依次添加到对应的bucket
                int digitOfElement = arr[j] / n % 10;//3
                //bucketElementCount[digitOfElement]表示第几组的，每一组都是0
                bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];//0
                bucketElementCount[digitOfElement]++;
            }
            int indexArr = 0;
            //二维数组里的值进行遍历，放到arr
            for (int k = 0; k < bucket.length; k++) {
                //判断列是否为空
                if (bucketElementCount[k] != 0) {
                    for (int l = 0; l < bucketElementCount[k]; l++) {
                        arr[indexArr++] = bucket[k][l];
                    }
                    //添加后，就要把bucketElementCount[k]置空，让后面轮次来使用
                    bucketElementCount[k] = 0;
                }
            }
            //System.out.println(Arrays.toString(arr))
        }


        /**
         * 第一轮
         * 1.将arr的数据根据个位数从小到大依次添加到二维数组
         * 2.将中转数组从小到大遍历取值，添加到arr
         */
//        for (int j = 0; j < arr.length; j++) {
//            //获取i数组值得个位数，然后根据个位数的值依次添加到对应的bucket
//            int digitOfElement = arr[j] % 10;//3
//            //bucketElementCount[digitOfElement]表示第几组的，每一组都是0
//            bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];//0
//            bucketElementCount[digitOfElement]++;
//        }
//        int indexArr=0;
//        //二维数组里的值进行遍历，放到arr
//        for (int k = 0; k < bucket.length; k++) {
//            //判断列是否为空
//            if (bucketElementCount[k]!=0) {
//                for (int l = 0; l < bucketElementCount[k]; l++) {
//                    arr[indexArr++]=bucket[k][l];
//                }
//                //添加后，就要把bucketElementCount[k]置空，让后面轮次来使用
//                 bucketElementCount[k]=0;
//            }
//        }
//        //System.out.println(Arrays.toString(arr))
        /**
         * 第二轮
         * 1.将arr的数据根据十位数从小到大依次添加到二维数组
         * 2.将中转数组从小到大遍历取值，添加到arr
         */
//        for (int j = 0; j < arr.length; j++) {
//            //获取i数组值得个位数，然后根据个位数的值依次添加到对应的bucket
//            int digitOfElement = arr[j]/10 % 10;//542--》4
//            //bucketElementCount[digitOfElement]表示第几组的，每一组都是0
//            bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];//0
//            bucketElementCount[digitOfElement]++;
//        }
//        indexArr=0;
//        //二维数组里的值进行遍历，放到arr
//        for (int k = 0; k < bucket.length; k++) {
//            //判断列是否为空
//            if (bucketElementCount[k]!=0) {
//                for (int l = 0; l < bucketElementCount[k]; l++) {
//                    arr[indexArr++]=bucket[k][l];
//                }
//                //添加后，就要把bucketElementCount[k]置空，让后面轮次来使用
//                bucketElementCount[k]=0;
//            }
//        }
//        //System.out.println(Arrays.toString(arr))
        /**
         * 第三轮
         * 1.将arr的数据根据百位数从小到大依次添加到二维数组
         * 2.将中转数组从小到大遍历取值，添加到arr
         */
//        for (int j = 0; j < arr.length; j++) {
//            //获取i数组值得个位数，然后根据个位数的值依次添加到对应的bucket
//            int digitOfElement = arr[j]/100 % 10;//542--》4
//            //bucketElementCount[digitOfElement]表示第几组的，每一组都是0
//            bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];//0
//            bucketElementCount[digitOfElement]++;
//        }
//        indexArr=0;
//        //二维数组里的值进行遍历，放到arr
//        for (int k = 0; k < bucket.length; k++) {
//            //判断列是否为空
//            if (bucketElementCount[k]!=0) {
//                for (int l = 0; l < bucketElementCount[k]; l++) {
//                    arr[indexArr++]=bucket[k][l];
//                }
//                //添加后，就要把bucketElementCount[k]置空，让后面轮次来使用
//                bucketElementCount[k]=0;
//            }
//        }
//        //System.out.println(Arrays.toString(arr))

    }

    private static void radixSortTestB(int[] arr) {
        //获取数组中最大的值，并获取其长度
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int length = String.valueOf(max).length();
        //辅助二维数组
        int[][] bucket = new int[10][arr.length];
        //辅助二维数组中，第几组的拥有值
        int[] bucketElementCount = new int[10];
        for (int i = 0,n=1; i < length; i++,n*=10) {//53,76,123,213,1,43
            /**
             * 假设遍历第一组，根据个位数从小到大依次添加到中转二维数组中，然后再从中转数组，依次添加到arr中
             */
            //假设获取个位数
            for (int j = 0; j < arr.length; j++) {
                int digitOfElement = arr[j]/n % 10;//获取个位数的值
                //添加到二维数组
                bucket[digitOfElement][bucketElementCount[digitOfElement]++] = arr[j];
            }
            int index=0;
            for (int k = 0; k < bucket.length; k++) {
                if (bucketElementCount[k]!=0) {//判断那个数组是否有值
                    for (int l = 0; l < bucketElementCount[k]; l++) {
                        arr[index++]=bucket[k][l];
                    }
                    bucketElementCount[k]=0;
                }
            }
            System.out.println(Arrays.toString(arr));

        }

    }
}
